#include <bits/stdc++.h>
using namespace std;

/*

*/

// 法一
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        // 创建差分数组，长度为nums.size()+1，初始值全为0
        // 差分数组用于高效记录区间操作
        vector<int> deltaArray(nums.size() + 1, 0);
        
        // 遍历每个查询，将区间[left,right]的操作次数记录到差分数组中
        for (const auto& query : queries) {
            int left = query[0];  // 区间左端点
            int right = query[1]; // 区间右端点
            deltaArray[left] += 1;    // 区间开始位置操作次数+1
            deltaArray[right + 1] -= 1; // 区间结束后一个位置操作次数-1，用于区间终止标记
        }
        
        // 根据差分数组还原出每个位置的实际操作次数
        vector<int> operationCounts;
        int currentOperations = 0;
        for (int delta : deltaArray) {
            currentOperations += delta;
            operationCounts.push_back(currentOperations);
        }
        
        // 检查每个位置的操作次数是否足够将对应元素减为0
        // 操作次数需大于等于nums中对应位置的元素值
        for (int i = 0; i < nums.size(); ++i) {
            if (operationCounts[i] < nums[i]) {
                return false; // 存在元素无法减为0，返回false
            }
        }
        
        // 所有元素都可以减为0，返回true
        return true;
    }
};

// 法二
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        // 构建差分数组来高效计算每个位置被覆盖的次数
        vector<int> delta(n + 1, 0);
        
        // 处理每个查询，统计每个位置被多少个查询区间覆盖
        for (const auto& q : queries) {
            int left = q[0], right = q[1];
            delta[left]++;
            if (right + 1 < n) delta[right + 1]--;
        }
        
        // 前缀和还原每个位置被覆盖的次数（即可执行的最大操作次数）
        vector<int> covered(n);
        covered[0] = delta[0];
        for (int i = 1; i < n; i++) {
            covered[i] = covered[i-1] + delta[i];
        }
        
        // 检查每个位置的最大可能操作次数是否足够将元素减为0
        for (int i = 0; i < n; i++) {
            if (covered[i] < nums[i]) return false;
        }
        
        return true;
    }
};

// 法三
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        // 创建差分数组，用于记录每个位置的操作次数变化量
        // 长度为nums.size()+1，确保处理右边界时不会越界
        std::vector<int> diff{};
        diff.resize(nums.size() + 1);
        
        // 遍历所有查询，构建差分数组
        // 对于每个查询[left, right]，在left位置+1表示操作开始，在right+1位置-1表示操作结束
        for (int i = 0; i < queries.size(); ++i) {
            diff[queries[i][0]] += 1;           // 区间开始位置操作次数+1
            diff[queries[i][1] + 1] -= 1;       // 区间结束位置后一位操作次数-1
        }
        
        // 前缀和变量，用于累加差分数组的值，得到当前位置的实际操作次数
        int sum_diff{};
        
        // 遍历数组，检查每个位置的操作次数是否足够将该位置元素减为0
        for (int i = 0; i < nums.size(); ++i) {
            sum_diff += diff[i];                // 累加差分值得到当前位置的操作次数
            if (nums[i] > sum_diff) {           // 如果当前位置的元素值大于可操作次数
                return false;                   // 则无法将该位置元素减为0，返回false
            }
        }
        
        // 所有元素都可以减为0，返回true
        return true;
    }
};
